#include <iostream>
#include <string>
using namespace std;
string replaceSpace(string s) {
	string ans;
	for (auto c : s) {
		if (c == ' ') {
			ans.push_back('%');
			ans.push_back('2');
			ans.push_back('0');
		}
		else {
			ans.push_back(c);
		}
	}
	return ans;
}

string replaceSpace2(string s) {
	int old = s.length();
	int newl = old;
	for (char c : s) {
		if (c == ' ') {
			newl += 2;
		}
	}
	s.resize(newl);
	int j = newl - 1;
	int i = old - 1;
	while (i>=0 && j>i) {
		if (s[i] == ' ') {
			s[j--] = '0';
			s[j--] = '2';
			s[j--] = '%';
		}
		else {
			s[j--] = s[i];
		}
		--i;
	}
	return s;
}
void test(char* name, string& s, string& exp) {
	if (name != nullptr) {
		cout << name << " begin:" << endl;
	}
	bool flag = true;
	cout << "Solution 1:" << endl;
	string ans = replaceSpace(s);
	if (ans.size() != exp.size()) {
		cout << "Failed" << endl;
	}
	else {
		for (int i = 0; i < (int)ans.size(); ++i) {
			if (ans[i] != exp[i]) {
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << "Passed!" << endl;
		}
		else {
			cout << "Failed" << endl;
		}
		
	}
	
	cout << "Solution 2:" << endl;
	ans = replaceSpace2(s);
	if (ans.size() != exp.size()) {
		cout << "Failed" << endl;
		return;
	}
	for (int i = 0; i < (int)ans.size(); ++i) {
		if (ans[i] != exp[i]) {
			cout << "Failed!" << endl;
			return;
		}
	}
	cout << "Passed!" << endl;
	return;		
}
void test1() {
	string s = "We are happy.";
	string exp = "We%20are%20happy.";
	test((char*)"test1", s, exp);
}
void test2() {
	string s = "hello world";
	string exp = "hello%20world";
	test((char*)"test2", s, exp);
}
void test3() {
	string s = " hello";
	string exp = "%20hello";
	test((char*)"test3",s,exp);
}
void test4() {
	string s = "hello  ";
	string exp = "hello%20%20";
	test((char*)"test4", s, exp);
}
int main() {
	test1();
	test2();
	test3();
	test4();
	return 0;
}